package main.Q1601_1700;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Q1601_1610 {
    public static void main(String[] args) {
        System.out.println("Question1601：");
        System.out.println("Question1602：");
        System.out.println("Question1603：设计停车系统");
        System.out.println("Question1604：");
        System.out.println("Question1605：给定行和列的和求可行矩阵");
        System.out.println("Question1606：");
        System.out.println("Question1607：");
        System.out.println("Question1608：特殊数组的特征值");
        System.out.println("Question1609：奇偶树");
        System.out.println("Question1610：");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Question1603 {
    int big, medium, small;

    public Question1603(int big, int medium, int small) {
        this.big = big;
        this.medium = medium;
        this.small = small;
    }

    public boolean addCar(int carType) {
        switch (carType) {
            case 1:
                if (big > 0) {
                    big--;
                    return true;
                } else return false;
            case 2:
                if (medium > 0) {
                    medium--;
                    return true;
                } else return false;
            case 3:
                if (small > 0) {
                    small--;
                    return true;
                } else return false;
        }
        return false;
    }
}

class Question1605 {
    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int n = rowSum.length, m = colSum.length;
        int[][] matrix = new int[n][m];
        int i = 0, j = 0;
        while (i < n && j < m) {
            int v = Math.min(rowSum[i], colSum[j]);
            matrix[i][j] = v;
            rowSum[i] -= v;
            colSum[j] -= v;
            if (rowSum[i] == 0) {
                i++;
            }
            if (colSum[j] == 0) {
                j++;
            }
        }
        return matrix;
    }
}

class Question1608 {
    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        if (nums[0] >= length) return length;//最小元素大于等于数组长度
        for (int i = 1; i < length; i++) {
            if (nums[length - i] >= i && nums[length - 1 - i] < i) return i;
        }
        return -1;
    }
}

class Question1609 {
    public boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            int curLevel = 0, lastCount = 1, curCount = 0;
            queue.add(root);
            while (!queue.isEmpty()) {
                int lastVal = -1;
                for (int i = 0; i < lastCount; i++) {
                    TreeNode node = queue.poll();//下层入栈计数
                    if (node.left != null) {
                        queue.add(node.left);
                        curCount++;
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                        curCount++;
                    }
                    if (curLevel % 2 == 0) {//偶数层
                        if (node.val % 2 == 0) {//奇数
                            return false;
                        } else {
                            if (lastVal == -1) {//首个节点
                                lastVal = node.val;
                            } else {
                                if (lastVal >= node.val) {//严格递增
                                    return false;
                                } else {
                                    lastVal = node.val;
                                }
                            }
                        }
                    } else {//奇数层
                        if (node.val % 2 != 0) {//偶数
                            return false;
                        } else {
                            if (lastVal == -1) {//首个节点
                                lastVal = node.val;
                            } else {
                                if (lastVal <= node.val) {//严格递减
                                    return false;
                                } else {
                                    lastVal = node.val;
                                }
                            }
                        }
                    }
                }
                curLevel++;
                lastCount = curCount;
                curCount = 0;
            }
        }
        return true;
    }
}